package leetcode.dynamic_programming;

/**
 * @author mgl
 * @version 1.0
 * @description 最小下降路径之和 leetcode第931题
 * @date 2023/10/6 16:25
 */
public class MinFallingPathSum {

    public int minFallingPathSum(int[][] matrix) {
        int row = matrix.length;
        int column = matrix[0].length;

        if (row == 1) return matrix[0][0]; //如果只有一行 那就是 1x1 直接返回第一个数字

        int[][] arr = new int[row][column];
        for (int i = 0; i < matrix[0].length; i++) {
            arr[0][i] = matrix[0][i];
        }

        for (int i = 1; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (j - 1 >= 0 && j + 1 < column) { //如果上面三个都可以取到的话 就取最小的
                    int min = arr[i - 1][j - 1];
                    for (int k = j; k < j + 2; k++) {
                        if (arr[i - 1][k] < min) min = arr[i - 1][k];
                    }
                    arr[i][j] = matrix[i][j] + min;
                } else if (j - 1 >= 0) { //如果j+1 越界了 只取 j 和 j-1
                    arr[i][j] = matrix[i][j] + Math.min(arr[i - 1][j - 1], arr[i - 1][j]);
                } else if (j + 1 < column) { //如果j-1 越界了 只取 j 和 j+1
                    arr[i][j] = matrix[i][j] + Math.min(arr[i - 1][j], arr[i - 1][j + 1]);
                }
            }
        }

        int[] _arr = arr[row - 1];
        int result = _arr[0];
        for (int i = 0; i < column; i++) { //遍历最后一行 取最小值
            if (_arr[i] < result) result = _arr[i];
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] arr = new int[][] {{-19,57},{-40,-5}};
        System.out.println(new MinFallingPathSum().minFallingPathSum(arr));
    }

}
